#pragma once
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <assert.h>
#include <queue>
#include "UnionFind.h"
#include <climits>
using namespace std;


//V：顶点	W：权值    false：无向图	true：有向图
template<class V, class W, W Max_W = INT_MAX,bool Direction = false >
class Graph
{
	struct Edge
	{
		int _srci;
		int _dsti;
		W _w;

		Edge(int srci, int dsti, const W& w)
			:_srci(srci)
			, _dsti(dsti)
			, _w(w)
		{}

		bool operator>(const Edge& e) const
		{
			return _w > e._w;
		}

	};

	typedef Graph<V, W> Self;

public:
	Graph() = default;
	
	Graph(const V* arr, size_t n)
	{
		_vertexs.reserve(n);
		for (int i = 0; i < n; ++i)
		{
			_vertexs.push_back(arr[i]);
			_map[arr[i]] = i;
		}

		_matrix.resize(n);
		for (int i = 0; i < n; ++i)
		{
			_matrix[i].resize(n, Max_W);
		}
	}

	//创建图
	void Creat(const V* arr, size_t n)
	{
		_vertexs.reserve(n);
		for (int i = 0; i < n; ++i)
		{
			_vertexs.push_back(arr[i]);
			_map[arr[i]] = i;
		}

		_matrix.resize(n);
		for (int i = 0; i < n; ++i)
		{
			_matrix[i].resize(n, Max_W);
		}
	}

	size_t GetVertexIndex(const V& v)
	{
		auto it = _map.find(v);
		if (it == _map.end())
		{
			assert(false);
			return -1;
		}
		return it->second;
	}

	//添加边
	void AddEdge(const V& src, const V& dst,const W& w)
	{
		size_t srci = GetVertexIndex(src);
		size_t dsti = GetVertexIndex(dst);

		_AddEdge(srci, dsti, w);
	}

	void Print()
	{
		for (int i = 0; i < _vertexs.size(); ++i)
		{
			for (int j = 0; j < _vertexs.size(); ++j)
			{
				if (_matrix[i][j] != INT_MAX)
					cout << "["<<_vertexs[i]<<"]->["<<_vertexs[j]<<"]: " << _matrix[i][j]  << endl;
			}
		}
	}

	//遍历
	void DFS(const V& src)
	{
		size_t srci = GetVertexIndex(src);
		size_t n = _vertexs.size();
		vector<bool> visited(n,false);

		_DFS(visited, srci);

		for (int i = 0; i < n; ++i)
		{
			if (_matrix[srci][i] != Max_W && visited[i] == false)
				_DFS(visited, i);
		}
	}

	void BFS(const V& src)
	{
		size_t srci = GetVertexIndex(src);
		size_t n = _vertexs.size();
		vector<bool> visited(_vertexs.size(), false);

		priority_queue<int> pq;
		pq.push(srci);
		visited[srci] = true;
		int level = 1;

		while (!pq.empty())
		{
			while (level--)
			{
				size_t front = pq.top();
				pq.pop();
				cout << _vertexs[front] << " ";
				for (int i = 0; i < n; ++i)
				{
					if (_matrix[front][i] != Max_W && visited[i] == false)
					{
						pq.push(i);
						visited[i] = true;
					}
				}
			}
			cout << endl;
			level = pq.size();
		}
	}
	
	W Kruskal(Self& minTree)
	{
		size_t n = _vertexs.size();
		minTree._vertexs = _vertexs;
		minTree._map = _map;
		minTree._matrix.resize(n);
		for (int i = 0; i < n; ++i)
		{
			minTree._matrix[i].resize(n, Max_W);
		}

		priority_queue<Edge,vector<Edge>,greater<Edge>> pq;

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
			{
				if (i < j && _matrix[i][j] != Max_W)
				{
					pq.push(Edge(i, j, _matrix[i][j]));
				}
			}

		size_t size = 0;
		W total = W();
		UnionFindSet<int> ufs(n);

		while (!pq.empty())
		{
			Edge e = pq.top();
			pq.pop();
			if (!ufs.InSet(e._srci, e._dsti))
			{
				ufs.Union(e._srci, e._dsti);
				minTree._matrix[e._srci][e._dsti] = _matrix[e._srci][e._dsti];
				size++;
				total += e._w;
			}
			if (size == n - 1)
				break;
		}

		if (size == n - 1)
		{
			return total;
		}
		return W();
	}

	W GetWeight()
	{
		W total = W();
		for (int i = 0; i < _vertexs.size(); ++i)
		{
			for (int j = 0; j < _vertexs.size(); ++j)
			{
				if ( _matrix[i][j] != Max_W)
				{
					total += _matrix[i][j];
				}
			}
		}
		return total;
	}

private:
	void _DFS(vector<bool>& visited, size_t srci)
	{
		cout << _vertexs[srci] << endl;
		visited[srci] = true;


		for (int i = 0; i < visited.size(); ++i)
		{
			if (_matrix[srci][i] != Max_W && visited[i] == false)
				_DFS(visited, i);
		}
	}

	void _AddEdge(size_t srci, size_t dsti, const W& w)
	{
		_matrix[srci][dsti] = w;
		if (Direction == false)
			_matrix[dsti][srci] = w;
	}

private:
	vector<vector<W>> _matrix; //边的集合
	vector<V> _vertexs;	//顶点集合
	map<V, int> _map;	//顶点转换
};

